A priority queue is a data structure that exposes a programmatic interface to retrieve queue entries or items from the priority queue according to a priority. For example, in a priority queue, entries or items within the priority queue that have a high priority may be processed or otherwise served before items with a lower priority.
A multi-core processor is a component in a computing environment with two or more independent central processing units (known as “CPUs” or “cores”), which are the units that read and execute program instructions, for example, in association with an application. Many-core processors and massively multi-core processors comprise, for example, multi-core architectures having an atypically high number of cores. For example, various many-core processors and massively multi-core processors have tens or hundreds of cores.
With the emergence of general-purpose graphics processing units (GPGPUs), powerful computing platforms are readily available to scientists and engineers. However, without the support of an efficient parallel priority queue, a significant class of related applications is not able to run on GPGPUs. Considering the nature of single instruction, multiple thread (SIMT) architecture, as well as the inefficient implementation of locks, developing an efficient parallel priority queue on GPGPUs has been an outstanding challenge.